package sort.yht;

import java.util.Arrays;
import sort.util.MySort;

/**
 * 功能描述：堆排序
 * @Author: yht
 * @Date: 2021/8/11 14:12
 */
public class Dui implements MySort {

  @Override
  public String getName() {
    return "【堆排序】";
  }

  @Override
  public int[] sort(int[] a) {
//    return doSort1(a);
//    return heapSort(a);//网上的方法，使用循环调整堆，速度稍快，比较省内存
    return doSort3(a);//我自己的方法，使用递调整堆，速度稍慢，也比较费内存
  }

  /**
   * 第一个版本
   * @param a
   * @return
   */
  private int[] doSort1(int[] a) {
    int max = a.length - 1, index;
    while (max > 0) {
      index = (max-1)/2;
      for(int i = index; i >= 0; i--) {
        if(2*i+2 <= max && a[2*i+1] < a[2*i+2]) exchange(a, 2*i+1, 2*i+2);
        if(a[i] < a[2*i+1]) exchange(a, i, 2*i+1);
      }
      exchange(a, 0, max);
      max--;
    }
    return a;
  }

  /**
   * 先初始化一个大顶堆
   *
   * 思路是，从堆底到堆顶，从右向左，比较父节点与左右叶子节点的大小
   * 如果某个父节点值小于子节点，则交换父子值
   *
   * 重点来了，交换后，子节点与子节点的子节点很可能大小关系发生变化
   * 所以要再从上到下从该节点开始微调该堆直到该节点以下符合大顶堆的特征
   *
   * @param a
   * @return
   */
  private int[] doSort3(int[] a) {
    int last = a.length - 1;
    for(int i = (last -1)/2; i >= 0; i--) {
      adjust(a, last, i);
    }
    while (last > 0) {
      exchange(a, 0, last--);
      adjust(a, last, 0);
    }
    return a;
  }

  /**
   * 该方法是在默认一个大顶堆的堆顶发生变化时调整该堆使其依旧是大顶堆
   *
   * 在默认堆某个节点以下原本符合大顶堆的前提下，该节点在此大顶堆的堆顶，
   * 当此节点值发生变化时，调节该节点以下的堆，使其依旧是一个大顶堆，
   * 也就是每个父节点的值都大于它的左右子节点
   *
   * 调节思路，从堆顶开始，比较其与左右子节点，假设右节点最大，则交换堆顶与其右节点的位置
   * 以右节点为堆顶向下重复此操作，直到再往下没有可调接的子节点为止
   *
   * @param a 需要排序的总数组
   * @param fm  需要调整的堆最末尾下标位置
   * @param f 需要调整的堆的堆顶位置
   */
  private void adjust(int[] a, int fm, int f){
    if(2*f+1 > fm) return;
    int bigger = 2*f+2 <= fm && a[2*f+1] < a[2*f+2] ? 2*f+2 : 2*f+1;
    if(a[f] < a[bigger]) {
      exchange(a, f, bigger);
      adjust(a, fm, bigger);
    }
  }

  /**
   * 测试是否为大顶堆（测试范围从坐标f到fm）
   * @param a 数组
   * @param fm 堆末下标
   * @param f 堆顶下标
   * @return
   */
  private boolean isBigHeap(int[] a, int fm, int f) {
    for(int k = f; 2*k+1 <= fm; k++) {
      if(a[k] < a[2*k+1] || ((2*k+2 <= fm) && a[k] < a[2*k+2])) {
        int[] arr = {a[k], a[2*k+1], 2*k+2 <= fm ? a[2*k+2] : 0};
        System.out.println(Arrays.toString(arr));
        return false;
      }
    }
    return true;
  }

  public static int [] heapSort(int [] arr) {
    int temp = 0;
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
      adjustHeap(arr,i,arr.length);
    }
    //交换
    for (int j = arr.length-1;j>0;j--){
      temp = arr[j];
      arr[j] = arr[0];
      arr[0] = temp;
      adjustHeap(arr,0,j);
    }
    return arr;
  }

  //将数组变为大顶推
  public static void adjustHeap(int arr[], int i, int length) {
    int temp = arr[i];
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
      if (k + 1 < length && arr[k] < arr[k + 1]) {
        k++;
      }
      if (arr[k] > temp) {
        arr[i] = arr[k];
        i = k;
      } else {
        break;
      }
    }
    arr[i] = temp;
  }

  public static void main(String[] args) {
    new Dui().testAll();
  }
}
